package reviewAlgorithms.math;

import java.util.PriorityQueue;
import java.util.Queue;

public class MaximumProduct {
    public static void main(String[] args) {
        int[] nums = {-5,-10,-1,-2,3,4,9};
        System.out.println(maximumProduct(nums));
        System.out.println(maximumProduct1(nums));
    }

    private static int maximumProduct1(int[] nums) {
        if (nums == null || nums.length < 3){
            return -1;
        }
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max1){
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            }else if (nums[i] > max2){
                max3 = max2;
                max2 = nums[i];
            }else if (nums[i] > max3){
                max3 = nums[i];
            }
            if (nums[i] < min1) {
                min2 = min1;
                min1 = nums[i];
            }else if (nums[i] < min2){
                min2 = nums[i];
            }
        }

        return Math.max(max1*max2*max3,min1*min2*max1);
    }

    public static int maximumProduct(int[] nums) {
        if (nums == null || nums.length < 3){
            return -1;
        }
        int res = 1;
        Queue<Integer> minQueueA = new PriorityQueue<>((o1,o2) -> (o2 - o1));
        Queue<Integer> minQueueN = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0){
                minQueueN.add(nums[i]);
            }
            minQueueA.add(nums[i]);
        }
        if (minQueueN.size() < 2){
            for (int i = 0; i < 3; i++) {
                if (!minQueueA.isEmpty()){
                    res *= minQueueA.poll();
                }
            }
        }else {
            if (!minQueueA.isEmpty()){
                int max = minQueueA.peek();
                for (int i = 0; i < 3; i++) {
                    if (!minQueueA.isEmpty()){
                        res *= minQueueA.poll();
                    }
                }
                int temp = 1;
                for (int i = 0; i < 2; i++) {
                    if (!minQueueN.isEmpty()){
                        temp *= minQueueN.poll();
                    }
                }
                temp *= max;
                res = Math.max(res,temp);
            }
        }
        return res;
    }
}
